package str

func StrStrByMySelf(haystack string, needle string) int {
	n1 := len(haystack)
	n2 := len(needle)

	// haystack needle均为空字符串
	if n1 == 0 && n2 == 0 {
		return 0
	}

	// haystack 为空字符串 needle不是
	if n1 == 0 {
		return -1
	}

	// needle为空字符串 haystack不是
	if n2 == 0 {
		return 0
	}

	// haystack比needle短
	if n1 < n2 {
		return -1
	}

	if n1 == n2 {
		if haystack == needle {
			return 0
		}
	}

	c := n1 - n2
	i := 0

	for i < c+1 {
		// 第一个字符匹配上便开始向后判断
		if haystack[i] == needle[0] {
			j := 0
			flag := true
			for j < n2 {
				if haystack[i+j] != needle[j] {
					flag = false
					break
				} else {
					j++
				}
			}
			if j == n2 && flag == true {
				return i
			}
		}
		i++
	}
	return -1
}

func StrStr(haystack string, needle string) int {
	n, m := len(haystack), len(needle)
	if m == 0 {
		return 0
	}
	pi := make([]int, m)
	for i, j := 1, 0; i < m; i++ {
		for j > 0 && needle[i] != needle[j] {
			j = pi[j-1]
		}
		if needle[i] == needle[j] {
			j++
		}
		pi[i] = j
	}
	for i, j := 0, 0; i < n; i++ {
		for j > 0 && haystack[i] != needle[j] {
			j = pi[j-1]
		}
		if haystack[i] == needle[j] {
			j++
		}
		if j == m {
			return i - m + 1
		}
	}
	return -1
}
